package leetcode.hot100;

import java.util.HashMap;

public class Solution494 {

    public static void main(String[] args) {
        int[] nums = new int[]{0,0,0,0,0,0,0,0,1};
        int target = 1;
        System.out.println(new Solution494().findTargetSumWays(nums,target));
    }


    //使用curMap存储当前为止和为key出现的次数value
    //使用lastMap存储上个元素为止和为key出现的次数value
    //foreach key in lastMap:
    // curMap[nums[i]+key] = lastMap[key],
    // curMap[-nums[i]+key] = lastMap[key]
    public int findTargetSumWays1(int[] nums, int target) {
        HashMap<Integer,Integer> lastMap = new HashMap<>();
        lastMap.put(0,1);
        HashMap<Integer,Integer> curMap = null;
        for (int num:nums) {
            curMap = new HashMap<>();
            for (int key:lastMap.keySet()) {
                int lastCount = lastMap.get(key);
                int addSum = key+num, subSum = key-num;
                curMap.put(addSum,curMap.getOrDefault(addSum,0)+lastCount);
                curMap.put(subSum,curMap.getOrDefault(subSum,0)+lastCount);
            }
            lastMap = curMap;
        }
        return lastMap.get(target);
    }

    //归结为背包问题：负号的数字和为neg，正号的和为sum-neg
    public int findTargetSumWays(int[] nums, int target) {
        //sum-neg-neg=target, neg=(sum-target)/2
        //问题归结为一个背包问题，找和为neg的所有组合
        int n = nums.length, sum = 0;
        for(int i=0;i<n;i++){
            sum += nums[i];
        }
        int neg = sum-target;
        if(neg<0||(neg&1)==1) return 0;
        neg >>=1;
        //开始dp
        int[][] dp = new int[n][neg+1];
        dp[0][0] = 1;
        if(nums[0]<=neg) dp[0][nums[0]]++;
        for(int i=1;i<n;i++){
            for(int j=0;j<=neg;j++){
                if(nums[i]>j) dp[i][j] = dp[i-1][j];
                else{
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];
                }
            }
        }
        return dp[n-1][neg];
    }
}
